package com.AC.ACShunfeng;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 租服务器
 */
public class test1 {



    // dp[i] = if(arr[i] > list.get(i)[0])Math.max(dp[i-1], dp[i-1] + list.get(i)[1])
    public int dp(int[] arr, List<int[]> list){
        int n = arr.length;
        int m = list.size();
        int sum = 0;
        for(int num : arr){
            sum += num;
        }

        int[][] dp = new int[m][sum];

        for(int i = 1; i<m; i++){
            for(int j = 1; j<sum; j++){
                if(list.get(i)[0] < j){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - list.get(i)[0]] + list.get(i)[0]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        return dp[m-1][sum-1];
    }

    public int greedy(int[] arr , List<int[]> list){
        int n = list.size();
        int m = arr.length;
        int sum = 0;
        for(int num : arr){
            sum += num;
        }
        int[][] dp = new int[n][sum];
        for(int i = 0; i<n; i++){
            int j = sum;
            int index = 0;
            while(j > 0){
                if(list.get(i)[0] < arr[index]){
                    int pre = dp[i][j];
                    dp[i][j] = Math.max(dp[i][j - arr[index]] + list.get(i)[1], dp[i][j]);
                    j -= arr[index];
                }
            }

        }


        return 0;
    }

    @Test
    public void test(){
        int[] arr = {1,2,3};
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{2,1});
        list.add(new int[]{3,2});
        list.add(new int[]{3,3});
        list.add(new int[]{1,1});
        greedy(arr,list);
    }
}
